package algorithms;


public class LinkedListOperations {
	public static void main(String [] args) {
		MyLinkedList operations1 = new MyLinkedList();
		operations1.add(1);
		operations1.add(2);
		operations1.add(3);
		operations1.add(4);
		
		MyLinkedList operations2 = new MyLinkedList();
		operations2.add(1);
		operations2.add(1);
		operations2.add(1);
		operations2.add(1);
		
		new LinkedListOperations().intersect(operations1, operations2).print();
		new LinkedListOperations().union(operations1, operations2).print();
	}
	
	public MyLinkedList intersect(MyLinkedList first, MyLinkedList second) {
		MyLinkedList result = new MyLinkedList();
		for (int i = 0; i < second.size(); i++) {
			int curr = first.get(i);
			for (int j = 0; j < first.size(); j++) {
				if (second.get(j) == curr) {
					result.add(curr);
					break;
				}
			}
		}
		
		return result;
	}
	
	public MyLinkedList union(MyLinkedList first, MyLinkedList second) {
		MyLinkedList result = new MyLinkedList();
		
		for (int i = 0; i < first.size(); i++) {
			int curr = first.get(i);
			if (!result.contains(curr)) {
				result.add(curr);
			}
		}
		
		for (int i = 0; i < second.size(); i++) {
			int curr = second.get(i);
			if (!result.contains(curr)) {
				result.add(curr);
			}
		}
		
		return result;
	}
	
}

class Node {
	int value;
	Node next;
	
	public Node(int value) {
		this.value = value;
	}
}

class MyLinkedList {
private Node first;
	
	public void add(int number) {
		if (first == null) {
			first = new Node(number);
		} else {
			Node curr = first;
			while (curr.next != null) {
				curr = curr.next;
			}
			curr.next = new Node(number);
		}
	}
	
	public int get(int position) {
		int res = -1;
		int i = 0;
		Node curr = first;
		while (i <= position) {
			res = curr.value;
			curr = curr.next;
			i++;
		}
		return res;
	}
	
	private Node getNode(int position) {
		int i = 0;
		Node curr = first;
		while (i < position) {
			curr = curr.next;
			i++;
		}
		
		return curr;
	}
	
	public boolean contains(int value) {
		boolean res = false;
		Node curr = first;
		while (curr != null) {
			if (curr.value == value) {
				res = true;
				break;
			}
			curr = curr.next;
		}
		return res;
	}
	
	public void delete(int pos) {
		if (first == null) {
			return;
		}
		
		if (pos == 0) {
			first = first.next;
		}
		
		Node curr = first;
		Node prev = curr;
		Node next = null;
		
		int i = 0;
		while (i < pos) {
			prev = curr;
			curr = curr.next;
			i++;
		}
		
		next = curr.next;
		prev.next = next;
		curr = null;
	}
	
	public int size() {
		int size = 0;
		Node curr = first;
		while (curr != null) {
			curr = curr.next;
			size++;
		}
		return size;
	}
	
	public void print() {
		for (int i = 0; i < size(); i++) {
			System.out.println(get(i));
		}
	}
	
}
